#! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq


class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def setChildren(self, left, right):
        self.left = left
        self.right = right

    def __lt__(self, other):
        if other is None or isinstance(other, Node):
            return False
        return self.freq > other.freq

    def __repr__(self):
        return "{0} - {1} - {2} - {3}".format(self.char, self.freq,
                                              self.left, self.right)


class HuffmanCoding:
    def __init__(self, path=None):
        self.path = path
        self.heap = []

    def makeFrequencyDict(self, text):
        frequency = {}
        for char in text:
            if char in frequency:
                frequency[char] += 1
            else:
                frequency[char] = 1
        return frequency

    def createHeap(self, frequency):
        for i, k in frequency.items():
            node = Node(i, k)
            heapq.heappush(self.heap, node)

    def createHuffTree(self):
        while len(self.heap) >= 2:
            node1 = heapq.heappop(self.heap)
            node2 = heapq.heappop(self.heap)
            merged = Node(None, node1.freq + node2.freq)
            merged.left, merged.right = node1, node2
            heapq.heappush(self.heap, merged)


# test
text = "aadnalhjjnmlhnawnlalhndn"
huffCoding = HuffmanCoding()
frequency = huffCoding.makeFrequencyDict(text)
huffCoding.createHeap(frequency)
huffCoding.createHuffTree()
print(huffCoding)